package mo.tags.stack;

import mo.common.TreeNode;

public class L1008 {

    public TreeNode bstFromPreorder(int[] preorder) {
        return bstFromPreorder(preorder, 0, preorder.length-1);
    }

    private TreeNode bstFromPreorder(int[] preorder, int from, int to) {
        if (from > to) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[from]);
        int right = -1;
        for (int i = from+1; i <= to; i++) {
            if (preorder[i] < preorder[from]) {
                right = i;
            } else {
                break;
            }
        }
        if (right != -1) {
            root.left = bstFromPreorder(preorder, from+1, right);
            root.right = bstFromPreorder(preorder, right+1, to);
        } else {
            root.right = bstFromPreorder(preorder, from+1, to);
        }
        return root;
    }

    public static void main(String[] args) {
        L1008 test = new L1008();
        TreeNode tree = test.bstFromPreorder(new int[]{4, 2});
        System.out.println(tree);
    }
}
